/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} succProb
 * @param {number} start
 * @param {number} end
 * @return {number}
 */
var maxProbability = function (n, edges, succProb, start, end) {
  let graph = []
  for (let i = 0; i < n; i++) {
    graph[i] = []
  }
  for (let i = 0; i < edges.length; i++) {
    let from = edges[i][0]
    let to = edges[i][1]
    let weight = succProb[i]
    graph[from].push([to, weight])
    graph[to].push([from, weight])
  }
  return dijkstra(start, end, graph)
};
class State {
  constructor(id, distFromStart) {
    this.id = id // 节点的id
    this.distFromStart = distFromStart // 从起点到节点的距离
  }
}
function dijkstra (start, end, graph) {
  let n = graph.length // 获得图的长度
  let distTo = new Array(n).fill(-1) // 因为是取概率 所以设置一个最小的取不到的 -1
  distTo[start] = 1 // 起点到起点的概率是1
  let pq = new myPriorityQueue() // 创建一个优先级队列 从大到小的顺序排了
  pq.enqueue(new State(start, 1), 1) // 这个的优先级就是这个的distFromStart 初始的概率是1
  while (!pq.isEmpty()) { // 如果队列不是空的话
    let curState = pq.dequeue().element // 队列弹出
    let curNodeId = curState.id // 获得弹出的元素的id
    let curDistFromStart = curState.distFromStart // 获得从起点到这个元素的距离
    if (curNodeId === end) {
      return curDistFromStart // 如果这个当前的id是结尾的id 那么直接返回起点到这个元素的距离就好了
    }
    if (curDistFromStart < distTo[curNodeId]) {
      // 如果从起点到这个元素的距离 大于distTo数组中当前节点的距离 就直接进行下一次循环
      continue
    }
    for (let neighbor of graph[curNodeId]) { // 拿出这个节点所有的邻居
      let nextNodeId = neighbor[0] // 获得这个邻居的id
      let distToNextNode = distTo[curNodeId] * neighbor[1] // 计算从起始节点到这个节点的概率
      if (distTo[nextNodeId] < distToNextNode) { // 如果现在的下一个节点的最短距离 大于从起始节点到该节点的距离 如果已经记录的概率 小于 计算的到的概率 那就让这个概率更新一下
        distTo[nextNodeId] = distToNextNode
        pq.enqueue(new State(nextNodeId, distToNextNode), distToNextNode) // 将当前的节点放入优先级队列 此时的权重是distToNextNode
      }
    }
  }
  return 0.0 // 如果走到这里说明从开始到不能走到最后 直接返回0
}
//封装优先级队列，priority越小，优先级越高
function myPriorityQueue () {
  //存放每一个插入元素QueueElement
  this.items = [];
  //定义内部类--封装插入元素
  function QueueElement (element, priority) {
    this.element = element;
    this.priority = priority;
  }
  //实现插入操作
  myPriorityQueue.prototype.enqueue = function (element, priority) {
    var qe = new QueueElement(element, priority);
    if (this.items.length === 0) {
      this.items.push(qe);
    } else {
      var flag = false; //记录元素是否插入，没有就插入到items最后
      for (var i = 0; i < this.items.length; i++) {
        if (priority > this.items[i].priority) {
          this.items.splice(i, 0, qe);
          flag = true;
          break;
        }
      }
      if (!flag) {	//没有就插入到items最后
        this.items.push(qe);
      }
    }
  }

  //2.将元素从队列中移除
  myPriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }
  //3.查看队列中第一个元素
  myPriorityQueue.prototype.front = function () {
    return this.items[0];
  }
  //4.查看队列是否为空
  myPriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }
  //5.查看队列中元素的个数
  myPriorityQueue.prototype.size = function () {
    return this.items.length;
  }
  //6.toString
  myPriorityQueue.prototype.toString = function () {
    var result = '';
    for (var i = 0; i < this.items.length; i++) {
      result += this.items[i].element + '---' + this.items[i].priority + ' ';
    }
    return result;
  }
}